package com.baidu.leetcode.palouti;

import java.util.HashMap;
import java.util.Map;

/**
 * @author shilei
 * @create 2023-04-07 21:32
 * 爬楼梯类似的题  传入n 最后几种解法
 * 凡是算法递归都可以破解 算法又叫穷举
 */
public class PaLouTi {

    //第一种暴力破解 递归
    public static int f1(int n){
        if (n <= 3) {
            return n;
        }
        return f1(n-1) + f1(n-2);
    }

    //第二种方法 带小本本的方法，将已经计算过的存起来 直接查
    public static int f2(int n,Map<Integer,Integer> map){
        if (n <= 3){
            return n;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        int left = f2(n - 1, map);
        int right = f2(n - 2, map);
        int total = left + right;
        map.put(n,total);
        return total;
    }

    //第三种方式 类似爬楼梯方式
    public static int f3(int n) {
        if (n <= 3){
            return n;
        }
        //记录从一个台阶到N个台阶中 每个台阶所需要的方法
        int[] dp = new int[n];
        dp[0] =1; //第一个台阶
        dp[1]=2; //第二台阶
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n-1];
    }

    //第四种方式
    public static int f4(int n){
        if (n <= 3){
            return n;
        }
        int left = 1;
        int right = 2;
        int total = 0;
        while ((n--) >2) {
            total = left + right;
            left = right;
            right = total;
        }
        return total;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(f1(30));
        System.out.println("暴力破解花费:"+(System.currentTimeMillis() - start));

        long start1 = System.currentTimeMillis();
        System.out.println(f2(30,new HashMap<>()));
        System.out.println("小本本破解花费:"+(System.currentTimeMillis() - start1));

        long start2 = System.currentTimeMillis();
        System.out.println(f3(30));
        System.out.println("动态规划破解花费:"+(System.currentTimeMillis() - start2));

        long start3 = System.currentTimeMillis();
        System.out.println(f4(30));
        System.out.println("动态规划破解花费:"+(System.currentTimeMillis() - start3));
    }
}
